package j2024.j202409;

public class j0919 {
    /**
     * 12. 整数转罗马数字
     * 七个不同的符号代表罗马数字，其值如下：
     *
     * 符号	值
     * I	1
     * V	5
     * X	10
     * L	50
     * C	100
     * D	500
     * M	1000
     * 罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
     *
     * 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，
     * 然后将其余部分转换为罗马数字。
     * 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I):
     * IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
     * 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。
     * 你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
     * 给定一个整数，将其转换为罗马数字
     * @param num
     * @return
     */
    public static String intToRoman(int num) {
        int[] key = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] val = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < key.length; i++) {
            if(num/key[i]!=0){
                int count = num/key[i];
                for (int j = 0; j < count; j++) {
                    ret.append(val[i]);
                }
                num%=key[i];
            }
            if(num==0){
                break;
            }
        }
        return ret.toString();
    }

    public static void main(String[] args) {
        intToRoman(3749);
    }

    /**
     * 58. 最后一个单词的长度
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。
     * 返回字符串中 最后一个 单词的长度。
     *
     * 单词 是指仅由字母组成、不包含任何空格字符的最大
     * 子字符串
     * 。
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        int n = s.length();
        int end = n-1;
        while(end>=0 && s.charAt(end)==' '){
            end--;
        }
        int index = end;
        while(index>=0 && s.charAt(index)!=' '){
            index--;
        }
        return end-index+1;
    }

    /**
     * 14. 最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        for (int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if(i==strs[j].length() || ch!=strs[j].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 151. 反转字符串中的单词
     * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
     *
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     *
     * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
     *
     * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。
     * 返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        s.trim();
        int n = s.length();
        int right = n-1,left = n-1;
        StringBuilder ret = new StringBuilder();
        while(left>=0){
            while(left>=0 && s.charAt(left)!=' '){
                left--;
            }
            ret.append(s.substring(left+1,right+1));
            ret.append(" ");
            while(left>=0 && s.charAt(left)==' '){
                left--;
            }
            right = left;
        }
        return ret.toString().trim();
    }
}
